package com.cjm.algorithm.backtracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Ti216 {
    public static void main(String[] args) {
        Ti216 ti216 = new Ti216();
        ti216.combinationSum3(3, 9);
        System.err.println("OK");
    }

    List<Integer> xx = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9);
    int max = 50;
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        res.clear();
        if (n > 50) {
            return res;
        }
        method216(0, k, n, new ArrayList<>(), 0);
        return res;
    }

    private void method216(int startIndex, int k, int n, ArrayList<Integer> objects, int cur) {
        if (cur > n) {
            return;
        }
        if (objects.size() > k) {
            return;
        }

        for (int i = startIndex; i < xx.size(); i++) {
            Integer currentValue = xx.get(i) + cur;
            if (currentValue > n) {
                return;
            }
            objects.add(xx.get(i));
            if (currentValue == n) {
                if (objects.size() == k) {
                    res.add(new ArrayList<>(objects));
                }
                objects.remove(objects.size() - 1);
                return;
            }
            method216(i + 1, k, n, objects, currentValue);
            objects.remove(objects.size() - 1);
        }

    }
}
